Some cryptographic operations such as encryption and decryption are based on Galois-Field (GF) arithmetic. Various implementations of Galois-Field arithmetic are known in the art. For example, in U.S. Pat. No. 4,322,577, whose disclosure is incorporated herein by reference, encryption and decryption of information of a message are performed by partitioning a plain text message into blocks of binary digits and by further partitioning the blocks into sub-blocks which are interpreted as elements in a Galois field. A plain text matrix (M) of the elements is multiplied by a first key matrix (A) of a group over the Galois field, the resulting product (M·A) being multiplied by a second key matrix (B) of the same group over the Galois field. The final product (B·M·A) thus received constitutes the encrypted message block (K). Decryption is performed by multiplying the transmitted product (B·M·A) by inverse key matrices (A−1, B−1)) generated by the same keys (a, b) as used for decryption and taken in the proper order.
U.S. Pat. No. 4,975,867, whose disclosure is incorporated herein by reference, describes an apparatus and/or method which enables one to divide two elements, A and B, of GF(22M), i.e., perform the operation B/A, by finding the multiplicative inverse of the divisor A, and then multiplying the inverse by the numerator, B. The multiplicative inverse, A−1, of A is found by computing a conversion factor, D, and then multiplying A by D to convert it to an element C, where C is also an element of a smaller Galois field, GF(2M), which is a subfield of GF(22M). Specifically, C is equal to A2M+1, or A2M·A, in the field GF(22M). Next, the multiplicative inverse, C−1, of C in GF(2M) is found by appropriately entering a stored look-up table containing the 2M elements of GF(2M). The multiplicative inverse, C−1, of C is thereafter converted, by multiplying it by the conversion factor D calculated above, to the element of GF(22M) which is the multiplicative inverse, A−1, of the original divisor, A. The multiplicative inverse, A−1, of A is then multiplied by B to calculate the quotient, B/A.
U.S. Pat. No. 6,766,345, whose disclosure is incorporated herein by reference, describes a Galois-Field multiplier system that includes a multiplier circuit for multiplying two polynomials with coefficients over a Galois field to obtain their product, a Galois-Field linear transformer circuit responsive to the multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial, and a storage circuit for supplying to the Galois-Field linear transformer circuit a set of coefficients for predicting the modulo remainder for predetermined irreducible polynomial.
In “GF(2K) multipliers based on Montgomery multiplication algorithm,” Proceedings of the 2004 IEEE International Symposium on Circuits and Systems (ISCAS 2004), May 23-26, 2004, Vancouver, Canada, whose disclosure is incorporated herein by reference, Fournaris et al. describe two Finite-Field multiplier architectures and VLSI implementations that use the Montgomery Multiplication Algorithm. The first architecture (Folded) is optimized in order to minimize the silicon covered area (gate count) and the second (Pipelined) is optimized in order to reduce the multiplication time delay. Both architectures are measured in terms of gate count-chip covered area and multiplication time delay and have more than adequate results in comparison with other known multipliers.